package Graph;

import java.util.*;

public class _207_CourseSchedule {
//    boolean[] check;
    //over time limited
    Map<Integer,List<Integer>> courses = new HashMap<>();
    public boolean canFinish_0(int numCourses, int[][] prerequisites) {
//        this.check = new boolean[numCourses];
        boolean res = true;
        for (int i = 0; i < prerequisites.length; i++) {
            if (!courses.containsKey(prerequisites[i][0])) {
                courses.put(prerequisites[i][0], new ArrayList<>());
            }
                courses.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        for (Map.Entry<Integer, List<Integer>> course : courses.entrySet()) {
            int index = course.getKey();
//            if (!check[index]) {
                res = checkDupli(index,new HashSet<>());
                if (res == false) {
                    return res;
//                }
            }
        }
        return res;
    }

    public boolean checkDupli(int index,Set set) {
//        check[index] = true;
        List<Integer> list = courses.get(index);
        if (list != null) {
            Set<Integer> dupli = new HashSet<>();
            dupli.addAll(set);
            dupli.add(index);
            for (int i : list) {
                if (dupli.contains(i)) {
                    return false;
                } else {
                    boolean check = checkDupli(i,dupli);
                    if (!check) {
                        return check;
                    }
                }
            }
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            graph[pre[1]].add(pre[0]);
            indegree[pre[0]]++;
        }
        //boolean[] inQ = new boolean[numCourses];
        Queue<Integer> q = new LinkedList();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }
        int cnt = 0;
        while (!q.isEmpty()) {
            int v = q.poll();
            cnt++;
            for (int w : graph[v]) {
                indegree[w]--;
                if (indegree[w] == 0) q.add(w);
            }
        }
        return cnt == numCourses;
    }
}
